Masala #1188

Xotira 128 MB Vaqt 1000 ms Qiyinchiligi 50 %

Massivlar soni

Uzunligi \(m\) ga teng butun sonlardan iborat \(a\) massividagi inversiyalar soni deb quyidagi shartlarni qanoatlantiruvchi \((i, j)\) juftliklar soniga aytiladi:

\(1≤i<j≤m\)
\(a_i >a_j\)

Siz \(1\) dan \(n\) gacha bo‘lgan butun sonlardan tashkil topgan \(n\) ta elementli (\(1\) dan \(n\) gacha bo‘lgan barcha butun sonlar bir martadan ishtirok etgan) inversiyalar soni \(k\) ga teng bo‘lgan massivlar sonini aniqlang. Bu son juda katta bo‘lishi mumkinligi sababli, uni \(10^9+7\) ga bo‘lgandagi qoldig‘ini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(n(1 ≤ n ≤ 1000)\) va \(k(0 ≤ k ≤ 10000)\) kiritiladi.

Chiquvchi ma'lumotlar:

Masala javobini \(10^9+7\) ga bo'lgandagi qoldig'ini chiqaring.

Misollar

#	input.txt	output.txt
1	10 1	9
2	4 3	6
3	9 13	17957

Izoh:

1-testda mumkin bo'lgan holatlar

1 - (2, 1, 3, 4, 5, 6, 7, 8, 9, 10)

2 - (1, 3, 2, 4, 5, 6, 7, 8, 9, 10)

3 - (1, 2, 4, 3, 5, 6, 7, 8, 9, 10)

4 - (1, 2, 3, 5, 4, 6, 7, 8, 9, 10)

5 - (1, 2, 3, 4, 6, 5, 7, 8, 9, 10)

6 - (1, 2, 3, 4, 5, 7, 6, 8, 9, 10)

7 - (1, 2, 3, 4, 5, 6, 8, 7, 9, 10)

8 - (1, 2, 3, 4, 5, 6, 7, 9, 8, 10)

9 - (1, 2, 3, 4, 5, 6, 7, 8, 10, 9)

Yuqoridagi barcha holatlarda inversiyalar soni 1 ga teng. Osongina ko'rish mumkin-ki boshqa holat mavjud emas.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin